package main

import "fmt"

func floodFill(image [][]int, sr int, sc int, newColor int) [][]int {
	newImage := make([][]int, 0)
	visited := make([][]bool, 0)
	for _, line := range image {
		newImage = append(newImage, line)
		visited = append(visited, make([]bool, len(line)))
	}
	dfs(image, sr, sc, image[sr][sc], newColor, newImage, visited)
	return newImage
}

func dfs(image [][]int, row, col int, targetColor, newColor int, newImage [][]int, visited [][]bool) {
	if image[row][col] != targetColor {
		return
	}
	newImage[row][col] = newColor
	visited[row][col] = true
	if row-1 >= 0 {
		if !visited[row-1][col] {
			visited[row-1][col] = true
			dfs(image, row-1, col, targetColor, newColor, newImage, visited)
		}
	}
	if row+1 < len(image) {
		if !visited[row+1][col] {
			visited[row+1][col] = true
			dfs(image, row+1, col, targetColor, newColor, newImage, visited)
		}
	}
	if col-1 >= 0 {
		if !visited[row][col-1] {
			visited[row][col-1] = true
			dfs(image, row, col-1, targetColor, newColor, newImage, visited)
		}
	}
	if col+1 < len(image[row]) {
		if !visited[row][col+1] {
			visited[row][col+1] = true
			dfs(image, row, col+1, targetColor, newColor, newImage, visited)
		}
	}
}

func main() {
	image := [][]int{
		{1, 1, 1},
		{1, 1, 0},
		{1, 0, 1},
	}
	sr := 1
	sc := 1
	newColor := 2
	fmt.Println(floodFill(image, sr, sc, newColor))
}
